#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod=10007;
struct matrix{
    ll a[5][5];
};
matrix multi(matrix a, matrix b)
{
    matrix ans;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
        {
            ans.a[i][j]=0;
            for(int k=1;k<=4;k++)
            {
                ans.a[i][j]+=a.a[i][k]*b.a[k][j];
                ans.a[i][j]%=mod;
            }
        }
    return ans;
}
matrix power(int num)
{
    matrix base;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
        {
            if(i==j)base.a[i][j]=2;
            else if(i+j==5)base.a[i][j]=0;
            else base.a[i][j]=1;
        }
    matrix ans;
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            if(i==j)ans.a[i][j]=1;
            else ans.a[i][j]=0;
    while(num>0)
    {
        if(num&1)
        {
            ans=multi(ans, base);
        }
        num>>=1;
        base=multi(base, base);
    }
    return ans;
}
int main()
{
    int t ;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        matrix ans=power(n);
        printf("%lld\n", ans.a[4][4]);
    }
}

